package javatest.algorith;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Strings {
    public String source;
    Strings(String source) {
        this.source = source;
    }
    public static void main(String[] args) {
        Strings s = new Strings("dsxd");
        System.out.println("Source String: " +  s.source+ "\n");
        
        HashSet<String> result = s.allSubsetOrderd();
        System.out.println("----- allSubsetOrderd -----");
        PriorityQueue<String> pq = new PriorityQueue<>(new LengthComprator());
        for(String r: result){
            pq.add(r);
        }
        while(!pq.isEmpty()){
            System.out.print(pq.poll()+", ");
        }
        System.out.println("\n\n");

        s = new Strings("qwertyusdfghjklzxghy");
       
        System.out.println("----- allSubset1 -----");
        long start = System.currentTimeMillis();
        ArrayList<String> result2 = s.allSubset();
        System.out.println(result2.size());
        long end = System.currentTimeMillis();
        System.out.println("--use time: " + (end - start));

        System.out.println("----- allSubset2 -----");
        start = System.currentTimeMillis();
        ArrayList<String> result3 = s.allSubset2();
        System.out.println(result3.size());
        end = System.currentTimeMillis();
        System.out.println("--use time: " + (end - start));

        System.out.println("----- allRank1 -----");
        s = new Strings("rtyuidsd");
        start = System.currentTimeMillis();
        System.out.println(s.allRank().size());
        end = System.currentTimeMillis();
        System.out.println("--use time: " + (end - start));

        System.out.println("----- allRank2 -----");
        start = System.currentTimeMillis();
        System.out.println(s.allRank2().size());
        end = System.currentTimeMillis();
        System.out.println("--use time: " + (end - start));
        
    }
    public static class LengthComprator implements Comparator<String>{

        @Override
        public int compare(String s1, String s2) {
            return s1.length() - s2.length();
        }
    }
    /*
     * 所有子集(区分排列顺序)
     */
    public HashSet<String> allSubsetOrderd(){
        HashSet<String> result = new HashSet<>();
        
        for(int i=0; i<source.length(); i++){
            result.add(String.valueOf(source.charAt(i)));    
        }
        result.addAll(addSubset(result, 1));
        
        return result;
    }

    private HashSet<String> addSubset(HashSet<String> result, int length){
        HashSet<String> nextResult = new HashSet<>();
        if (result.isEmpty() || length == source.length()) return nextResult;
        for (String r: result){
            String nexts = source;

            for (int i=0; i<r.length(); i++){
                nexts = nexts.replaceFirst(String.valueOf(r.charAt(i)), "");
            }

            for (int j=0; j<nexts.length(); j++){
                nextResult.add(r + nexts.charAt(j));
            }
        }
        
        nextResult.addAll(addSubset(nextResult, length++));
        return nextResult;
    }
    /*
     * 所有自己(忽略字符顺序)
     */
    public ArrayList<String> allSubset(){
        ArrayList<String> result = new ArrayList<>();
        if (source == null) return result;
        result.add("");
        if (source == "") return result;
        addSubset(result, source.charAt(0), 0);
        return result;
    }

    private void addSubset(ArrayList<String> result, char next, int index){
        int length = source.length();
        
        if(index < length){
            int size = result.size();
            for(int i=0; i<size; i++){
                result.add(result.get(i) + next);
            }
            if (++index < length)
            addSubset(result, source.charAt(index), index);
        }
    }
    
    public ArrayList<String> allSubset2(){
        ArrayList<String> result = new ArrayList<>();
        char[] chars = source.toCharArray();
        process(result, chars, 0);
        return result;
    }
    private void process(ArrayList<String> result, char[] str, int index){
        if(index==str.length) {
            result.add(String.valueOf(str));
            return;
        }
        process(result, str, index+1);
        char a = str[index];
        str[index] = 0;
        process(result, str, index+1);
        str[index] = a;
    }
    /*
     * 所有排列
     */
    public ArrayList<String> allRank(){
        char[] chs = source.toCharArray();
        ArrayList<String> res = new ArrayList<>();
        
        processRank(chs, 0, res);

        return res;
    }
    private void processRank(char[] str, int i, ArrayList<String> res){
        if ( i == str.length ){
            res.add(String.valueOf(str));
        }
        boolean[] visit = new boolean[26];
        for ( int j=i; j< str.length; j++) {
            if(!visit[str[j] - 'a']){
                visit[str[j] - 'a'] = true;
                swap(str, i, j);
                processRank(str, i+1, res);
                swap(str, i, j);
            }
        }
    }
    private void swap(char[] chs, int i, int j){
        char temp = chs[i];
        chs[i] = chs[j];
        chs[j] = temp;
    }

    public ArrayList<String> allRank2(){
        char[] chs = source.toCharArray();
        return processRank2(chs);
    }
    private ArrayList<String> processRank2(char[] prev){
        ArrayList<String> res = new ArrayList<>();
        if (prev.length == 1){
            res.add(String.valueOf(prev[0]));
            return res;
        }
        ArrayList<String> prevResult = processRank2(Arrays.copyOfRange(prev, 0, prev.length-1));
        char last = prev[prev.length-1];
        for(int i=0; i< prevResult.size(); i++){
            String r = prevResult.get(i);
            for(int j=0; j<r.length(); j++){
                res.add(new StringBuilder(r).insert(j, last).toString());
            }
            res.add(r+last);
        }
        
        return res;
    }

    // public void allRank3(){
    //     char[] chs = source.toCharArray();
    //     ArrayList<String> res = new ArrayList<>();
    //     processs(chs, 0, res);
    // }
    // public String processs(char[] str, int i, ArrayList<String> res){
    //     if(i == str.length) return String.valueOf(str);
    //     for(int j=i; j<str.length; j++){

    //     }

    // }
}
